package com.zdy.demo;



import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 23 题， 层序遍历二叉树
 *
 * @author deyou
 * @version 1.0
 * @date 2021/5/21 8:45
 */

//class TreeNode{
//    int val;
//    TreeNode left;
//    TreeNode right;
//    TreeNode(int val){
//        this.val = val;
//    }
//}

/**
 *
 */
public class PrintFromTopToBottom23 {
    /**
     * 利用队列特性， 先进先出，先把父节点放入队里，然后弹出并把值放入list 数组链表，判断是否有子节点，有的话存入队列。
     * 递归调用循环输出。
     * @param root
     * @return
     */
    public static ArrayList<Integer> PrintFromTopToBottom(TreeNode root){
        //新建数组列表
        ArrayList<Integer> list = new ArrayList<>();
        if(root == null){
            return null;
        }
        //创建队列
        Queue<TreeNode> queue = new LinkedList<>();
        //将二叉树根节点放入队列中
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();//获取根节点,并出队
            list.add(node.val);  //将根节点数据放入list
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
        return list;
    }

    /***
     * 解法二: 利用递归, 利用递归调用自身，将数据存入list 集合
     *
     */

    public static ArrayList<Integer> PrintFromTopToBottom2(TreeNode root){
        ArrayList<Integer> list = new ArrayList<>();
        if(root == null){
            return null;
        }
        list.add(root.val);
        levelOrder(root,list);
        return list;

    }

    public static ArrayList<Integer> levelOrder(TreeNode root, ArrayList<Integer> list){
        if(root == null){
            return null;
        }
        if(root.left != null){
            list.add(root.left.val);
        }
        if(root.right != null){
            list.add(root.right.val);
        }
        levelOrder(root.left,list);
        levelOrder(root.right,list);
        return list;
    }
}
